//Given two non-negative integers num1 and num2 represented as strings, return t
//he product of num1 and num2, also represented as a string. 
//
// Note: You must not use any built-in BigInteger library or convert the inputs 
//to integer directly. 
//
// 
// Example 1: 
// Input: num1 = "2", num2 = "3"
//Output: "6"
// Example 2: 
// Input: num1 = "123", num2 = "456"
//Output: "56088"
// 
// 
// Constraints: 
//
// 
// 1 <= num1.length, num2.length <= 200 
// num1 and num2 consist of digits only. 
// Both num1 and num2 do not contain any leading zero, except the number 0 itsel
//f. 
// 
// Related Topics 数学 字符串 
// 👍 638 👎 0


package leetcode.editor.cn;

//Java：Multiply Strings
class P43MultiplyStrings {
    public static void main(String[] args) {
        Solution solution = new P43MultiplyStrings().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String multiply(String num1, String num2) {
            int m = num1.length(), n = num2.length();
            int[] arr = new int[m + n];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                    int p1 = i + j, p2 = i + j + 1;
                    int sum = mul + arr[p2];
                    arr[p2] = sum % 10;
                    arr[p1] += sum / 10;
                }
            }
            int i = 0;
            while (i < arr.length && arr[i] == 0) {
                i++;
            }
            String str = "";
            for (; i < arr.length; i++) {
                str = str + arr[i];
            }
            return str.length() == 0 ? "0" : str;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}